1. Field of the Invention
The present invention relates to a mobile communication system. More particularly, the present invention relates to an apparatus and method for generating Low Density Parity Check (LDPC) codes for sequential decoding.
2. Description of the Related Art
As mobile communication systems have been rapidly developing, there is an increasing demand for the development of technologies capable of transmitting a large volume of data in a wireless network with a similar level of performance to that of a wired network. To address the demand for a high-speed capable service, high-capacity communication systems are being developed that are capable of processing and transmitting a variety of information such as image and wireless data, beyond the voice-oriented services. The high-capacity communication systems being developed increase the system transmission efficiency using a channel encoding scheme that improves system performance. Therefore, the next-generation mobile communication system requires high-performance channel codes. To meet the above identified demands, research is being conducted on Low Density Parity Check (LDPC) codes that have superior binary error rate performance (i.e. lower binary error rate) through iterative decoding.
The LDPC codes are each defined by a parity check matrix H, and its performance is also determined according to a characteristic of the matrix H. Therefore, there is a need for a method for generating a high-performance matrix H.
FIG. 1 is a conceptual diagram schematically illustrating structures of a transmission part and a reception part of a communication system according to the conventional art.
Referring to FIG. 1, when a signal input to an input unit 100 is assumed to be i, the input unit 100 outputs the input signal i to a channel encoder 102. The channel encoder 102 channel-encodes the signal i with a preset channel encoding scheme, and outputs the channel-encoded signal c to a modulator 104. The modulator 104 modulates the signal c with a preset modulation scheme, and outputs the modulated signal m to a transmitter 106. The transmitter 106 performs transmission processing on the modulated signal m, and transmits the transmission-processed signal s to a reception part through a channel 108. The structure from the input unit 100 to the transmitter 106 corresponds to the transmission part of the communication system.
The reception part for restoring the signal received through the channel 108 is made in a reverse process of the transmission part. A receiver 110 performs reception processing on a signal r received through the channel 108, and outputs the reception-processed signal m′ to a demodulator 112. The demodulator 112 demodulates the signal m′ with a demodulation scheme corresponding to the modulation scheme of the modulator 104, and outputs the demodulated signal c′ to a channel decoder 114. The channel decoder 114 channel-decodes the signal c′ with a channel decoding scheme corresponding to the channel encoding scheme of the channel encoder 102, and outputs the channel-decoded signal i′ to an output unit 116. The structure from the receiver 110 to the output unit 116 corresponds to the reception part of the communication system.
The LDPC codes used in the transmission part of the communication system are a type of linear codes, and are defined as a parity check matrix in which the number of elements having a non-zero value is less than the number of elements having a zero value. The LDPC codes, which were originally proposed by Gallager in the early 1960s, are presently undergoing research in several fields as they were rediscovered in the late 1990s together with an increased interest in the codes capable of undergoing iterative decoding. The research on the LDPC codes is roughly divided into research on an algorithm for the generation of codes and research on an algorithm for the decoding the codes. Compared with turbo codes, which are another example of codes capable of undergoing iterative decoding, the LDPC codes are lower in decoding complexity, but have a greater encoding complexity. Therefore, research is being conducted on the design of the LDPC codes with reduced encoding complexity, or the LDPC codes that have a higher error correction performance.
Herein, the LDPC codes are expressed as a parity check matrix H in order to easily describe a structure of the LDPC codes. Meanwhile, when the parity check matrix H is expressed with a bipartite graph, rows of the parity check matrix H are associated with (or mapped to) check nodes, and columns of the parity check matrix H are associated with variable nodes. In the parity check matrix H, elements having a non-zero value are associated with edges between check nodes and variable nodes of the corresponding elements. Rows, columns and elements having a non-zero value of the parity check matrix H are used to denote similar meanings as check nodes, variable nodes and edges of the bipartite graph, respectively. In addition, when the parity check matrix H is expressed with the bipartite graph, the parity check matrix H can be expressed by distribution of degrees of the variable nodes and check nodes, and an arrangement of edges between the variable nodes and check nodes. A generation method of the parity check matrix H is determined by these two matters (i.e. degree distribution and edge arrangement). The term ‘degree’ as used herein refers to the number of edges connected to each of the variable nodes or check nodes. That is, as for an arbitrary variable node, if the number of edges connected to the variable node is assumed to be 2, a degree of the variable node is 2.
For general binary codes, the parity check matrix H is composed of values of ‘0’ and values of non-zero, for example, ‘1’. The method of generating the parity check matrix H first determines a degree of each variable node through a density evolution function, and arranges ‘1’s according to the determined degree. That is, the method connects edges between the variable nodes and the check nodes according to the determined degree. Typically, the algorithm for arranging ‘1’s in the parity check matrix H includes a Progressive Edge Growth (PEG) algorithm. The PEG algorithm, when connecting edges while sequentially adding variable nodes on the bipartite graph, connects one edge, and then selects and connects one edge among the edges so that a cycle passing through the variable nodes becomes the longest in the tree structure made at this time. The term ‘cycle’ as used herein refers to a series of edges when the edges connected beginning at a node return to their first start node. A length of the cycle refers to the total number of edges constituting the cycle.
Using the cycle concept, it is possible to increase a partial girth by connecting edges so that they have a longer cycle if possible at a small-sized code. The term ‘girth’ as used herein refers to a length of the shortest cycle among several cycles. Besides, the algorithm for arranging ‘1’s in the parity check matrix H includes an Approximate Cycle Extrinsic (ACE) algorithm for connecting edges such that when a short cycle is generated, there are many edges connected to the exterior.
In this way, the existing PEG algorithm or most methods similar thereto, are aimed at generating the parity check matrix H so that a length of the partial cycle increases. In addition, the parity check matrix H generated with the PEG algorithm is better in cycle characteristic than the randomly generated parity check matrix H, and use of a sum-product algorithm can improve code performance since independency between messages is secured at an initial iteration.
Meanwhile, a decoding algorithm can be defined on the bipartite graph, and in this case, flooding scheduling, which is a parallel decoding, can be applied. However, in actual realization of the decoding algorithm, a sequential decoding scheme having a lower complexity is implemented since the parallel decoding scheme has very high complexity. Further, the sequential decoding scheme is used because when a parity check matrix H is generated with the general PEG algorithm in the parallel decoding scheme, information obtained therethrough is not reflected in the information obtained from the next subset, or a ratio of the reflection, if any, can decrease. Therefore, it is possible to expect an improvement of decoding performance by designing the parity check matrix H in consideration of sequential decoding.